package com.zjsru.oneDay202210;

/**
 * @Author: CookLee
 * @Date: 2022/10/16
 * 可能的二分法
 * 给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和  bi的人归入同一组。
 *
 * 输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
 * 输出：true
 * 解释：group1 [1,4], group2 [2,3]
 *
 * 输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
 * 输出：false
 */
public class PossibleBipartition {
    
    int[] p = new int[4010];
    
    int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
    
    void union(int a, int b) {
        p[find(a)] = p[find(b)];
    }
    
    boolean query(int a, int b) {
        return find(a) == find(b);
    }
    
    /**
     * 反向点 + 并查集 即对于 (a,b) 和 (b,c)可知 a 和 c 位于同一集合。
     * <p>
     * 因此，我们可以对于每个点 x 而言，建议一个反向点 x + n：若点 x 位于集合 A 则其反向点 x + n 位于集合 B，反之同理。
     */
    public boolean possibleBipartition(int n, int[][] dislikes) {
        for (int i = 0; i < 2 * n; i++) {
            p[i] = i;
        }
        for (int[] info : dislikes) {
            int a = info[0];
            int b = info[1];
            if (query(a, b)) {
                return false;
            }
            union(a, b + n);
            union(a + n, b);
        }
        return true;
    }
    
    public static void main(String[] args) {
        PossibleBipartition possibleBipartition = new PossibleBipartition();
        int n = 4;
        int[][] dislikes = new int[][]{{1,2},{1,3},{2,4}};
        System.out.println(possibleBipartition.possibleBipartition(n, dislikes));
    }
}
